﻿// 0815train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>

using namespace std;

/*
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
 */

class Solution {
public:
    int result = 0;
    int findTargetSumWays(vector<int>& nums, int target)
    {
        if (nums.empty()) return 0;
        traceBack(nums, 0, target);
        return result;
	    //findTargetSumWays
    }
    void traceBack(vector<int>& nums, int i, int remain)
    {
        //1回溯终止的条件
        //i==nums.size()说明此时所有的数已处理完
        if (i==nums.size())
        {
            if (remain==0)
            {
                result++;
            }
            return;
        }

        //选择负号-，remain需要凑更多正数
        remain += nums[i];
        traceBack(nums, i + 1, remain);
        //撤销选择
        remain -= nums[i];

        //选择正号，remain凑更多负数
        remain -= nums[i];
        traceBack(nums, i + 1, remain);
        //撤销选项
        remain += nums[i];

        //traceBack------
    }
};



int main()
{
    //nums = [1,1,1,1,1], target = 3
    vector<int>nums = { 1,1,1,1,1 };
    int target = 3;
    Solution solu;
    cout<<solu.findTargetSumWays(nums, target);


}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
